//给定一个整数数组 A，返回 A 中最长等差子序列的长度。 
//
// 回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= A
//.length - 1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。 
//
// 
//
// 示例 1： 
//
// 输入：[3,6,9,12]
//输出：4
//解释： 
//整个数组是公差为 3 的等差数列。
// 
//
// 示例 2： 
//
// 输入：[9,4,7,2,10]
//输出：3
//解释：
//最长的等差子序列是 [4,7,10]。
// 
//
// 示例 3： 
//
// 输入：[20,1,15,3,10,5,8]
//输出：4
//解释：
//最长的等差子序列是 [20,15,10,5]。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= A.length <= 2000 
// 0 <= A[i] <= 10000 
// 
// Related Topics 动态规划 
// 👍 107 👎 0


package com.yun.leetcode.editor.cn;

import java.util.HashMap;

public class LongestArithmeticSubsequence {
    public static void main(String[] args) {
        Solution solution = new LongestArithmeticSubsequence().new Solution();
        solution.longestArithSeqLength(new int[]{3, 6, 9, 12});
    }

    /**
     * '''
     * 动态规划思路：以每个元素作为等差数列终点，计算出该数列长度，选择出最大值返回即可。
     * 在每个位置上，以字典结构保存该位置元素与前面每个位置上元素的差值，与对应该差值的数列长度。
     * '''
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 直接抄别人的。。
        public int longestArithSeqLength(int[] A) {
            int res = 0;

            int len = A.length;
            int[][] dp = new int[len][20002];
            int offset = 10000;

            for (int i = 0; i < dp.length; i++) {
                for (int j = 0; j < dp[0].length; j++) {
                    dp[i][j] = 1;
                }
            }

            for (int i = 1; i < len; i++) {
                for (int j = 0; j < i; j++) {
                    int sub = A[i] - A[j];
                    dp[i][sub + offset] = Math.max(dp[i][sub + offset], dp[j][sub + offset] + 1);
                    res = Math.max(res, dp[i][sub + offset]);
                }
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}